/* 中序非递归遍历二叉树 */

#include <iostream>
#include "BiTreefun.h"
using namespace std;
#define maxsize 50

// 中序非递归遍历
void Nonin(BTNode *bt)
{
  // 创建栈 -- 存储待访问的结点
  BTNode *Stack[maxsize];
  int top = -1;
  
  // 如果栈不为空 或者 结点不为空
  while (top != -1 || bt)
  {
    // 结点不为空
    if (bt != NULL)
    {
      // 进栈
      Stack[++top] = bt;
      
      // 到左孩子结点
      bt = bt->lchild;
    }
    
    // 结点为空
    else
    {
      // 出栈
      bt = Stack[top--];
      
      // 打印值
      cout << bt->data << " ";
      
      // 到右孩子结点
      bt = bt->rchild;
    }
  }
}

int main()
{
  // 创建二叉树
  BTNode *T = create_bitree();
  
  // 中序非递归遍历
  Nonin(T);
}